package com.nowcoder.code.lcof;

import java.util.Arrays;

public class JZ51 {

    public static void main(String[] args) {

        int[] is = new int[]{364, 637, 341, 406, 747, 995, 234, 971, 571, 219, 993, 407, 416, 366, 315, 301, 601, 650, 418, 355, 460, 505, 360, 965, 516, 648, 727, 667, 465, 849, 455, 181, 486, 149, 588, 233, 144, 174, 557, 67, 746, 550, 474, 162, 268, 142, 463, 221, 882, 576, 604, 739, 288, 569, 256, 936, 275, 401, 497, 82, 935, 983, 583, 523, 697, 478, 147, 795, 380, 973, 958, 115, 773, 870, 259, 655, 446, 863, 735, 784, 3, 671, 433, 630, 425, 930, 64, 266, 235, 187, 284, 665, 874, 80, 45, 848, 38, 811, 267, 575};
//        int[] is = new int[]{1,2,3,4,5,6,7,8,0};
        new JZ51().mergeSort(is, new int[is.length], 0, is.length - 1);
        System.out.println(Arrays.toString(is));
        System.out.println(sum);

    }

    public int InversePairs(int[] nums) {
        mergeSort(nums, new int[nums.length],0, nums.length - 1);
        return sum;
    }

    static int sum = 0;


    public void mergeSort(int[] is, int[] tmp, int start, int end) {
        if (start >= end) {
            return;
        }
        int middle = (start + end) >> 1;
        mergeSort(is, tmp, start, middle);
        mergeSort(is, tmp, middle + 1, end);
        int mm = middle + 1;
        int s = start;
        int i = s;
        while (s <= middle && mm <= end) {
            if (is[s] < is[mm]) {
                tmp[i] = is[s];
                s++;
            } else {
                tmp[i] = is[mm];
                mm++;
                sum = sum + middle - s + 1;
            }
            i++;
        }

        while (s <= middle || mm <= end) {
            if (s <= middle) {
                tmp[i] = is[s];
                s++;
            }
            if (mm <= end) {
                tmp[i] = is[mm];
                mm++;
            }
            i++;
        }

        for (i = start; i <= end; i++) {
            is[i] = tmp[i];
        }

    }


    public void quickSort(int[] is, int start, int end) {
        if (start >= end) {
            return;
        }
        int middle = (start + end) >> 1;
        int mi = is[middle];
        int s = start;
        int e = end;
        while (s < e) {
            while (s < e && is[e] > mi) {
                e--;
            }
            while (s < e && is[s] < mi) {
                s++;
            }
            if (s < e) {
                int tmp = is[s];
                is[s] = is[e];
                is[e] = tmp;
                sum = sum + 1;
            }
        }

        quickSort(is, start, s);
        quickSort(is, s + 1, end);

    }

}
